In the High efficiency video coding (HEVC) that is an international video coding standard, coding is performed for each coding unit (CU) as a unit of coding. In the conventional H. 264 etc., 16 pixels high and 16 pixels wide are used as a macroblock size. On the other hand, four kinds of sizes can be used as CU sizes. In addition, various sizes can be selected for prediction units (PUs) used for intra prediction in CUs and transform units (TUs) which are units of orthogonal transform (for example, see Non-patent Literature 1).